64. Minimum Path Sum
Medium

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right, which minimizes the sum of all numbers along its path.

Note: You can only move either down or right at any point in time.

 

Example 1:

Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Because the path 1 → 3 → 1 → 1 → 1 minimizes the sum.

Example 2:

Input: grid = [[1,2,3],[4,5,6]]
Output: 12

 

Constraints:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 200
  • 0 <= grid[i][j] <= 100
Accepted
548,154
Submissions
963,282
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.19 (47 votes)

Premium

Summary

We have to find the minimum sum of numbers over a path from the top left to the bottom right of the given matrix .

Solution


Approach 1: Brute Force

The Brute Force approach involves recursion. For each element, we consider two paths, rightwards and downwards and find the minimum sum out of those two. It specifies whether we need to take a right step or downward step to minimize the sum.

cost(i,j)=grid[i][j]+min(cost(i+1,j),cost(i,j+1)) \mathrm{cost}(i, j)=\mathrm{grid}[i][j] + \min \big(\mathrm{cost}(i+1, j), \mathrm{cost}(i, j+1) \big)

Complexity Analysis

  • Time complexity : O(2m+n)O\big(2^{m+n}\big). For every move, we have atmost 2 options.
  • Space complexity : O(m+n)O(m+n). Recursion of depth m+nm+n.


Approach 2: Dynamic Programming 2D

Algorithm

We use an extra matrix dpdp of the same size as the original matrix. In this matrix, dp(i,j)dp(i, j) represents the minimum sum of the path from the index (i,j)(i, j) to the bottom rightmost element. We start by initializing the bottom rightmost element of dpdp as the last element of the given matrix. Then for each element starting from the bottom right, we traverse backwards and fill in the matrix with the required minimum sums. Now, we need to note that at every element, we can move either rightwards or downwards. Therefore, for filling in the minimum sum, we use the equation:

dp(i,j)=grid(i,j)+min(dp(i+1,j),dp(i,j+1)) dp(i, j)= \mathrm{grid}(i,j)+\min\big(dp(i+1,j),dp(i,j+1)\big)

taking care of the boundary conditions.

The following figure illustrates the process:

Current
1 / 17

Complexity Analysis

  • Time complexity : O(mn)O(mn). We traverse the entire matrix once.

  • Space complexity : O(mn)O(mn). Another matrix of the same size is used.


Approach 3: Dynamic Programming 1D

Algorithm

In the previous case, instead of using a 2D matrix for dp, we can do the same work using a dpdp array of the row size, since for making the current entry all we need is the dp entry for the bottom and the right element. Thus, we start by initializing only the last element of the array as the last element of the given matrix. The last entry is the bottom rightmost element of the given matrix. Then, we start moving towards the left and update the entry dp(j)dp(j) as:

dp(j)=grid(i,j)+min(dp(j),dp(j+1)) dp(j)=\mathrm{grid}(i,j)+\min\big(dp(j),dp(j+1)\big)

We repeat the same process for every row as we move upwards. At the end dp(0)dp(0) gives the required minimum sum.

Complexity Analysis

  • Time complexity : O(mn)O(mn). We traverse the entire matrix once.

  • Space complexity : O(n)O(n). Another array of row size is used.


Approach 4: Dynamic Programming (Without Extra Space)

Algorithm

This approach is same as Approach 2, with a slight difference. Instead of using another dpdp matrix. We can store the minimum sums in the original matrix itself, since we need not retain the original matrix here. Thus, the governing equation now becomes:

grid(i,j)=grid(i,j)+min(grid(i+1,j),grid(i,j+1)) \mathrm{grid}(i, j)=\mathrm{grid}(i,j)+\min \big(\mathrm{grid}(i+1,j), \mathrm{grid}(i,j+1)\big)

Complexity Analysis

  • Time complexity : O(mn)O(mn). We traverse the entire matrix once.

  • Space complexity : O(1)O(1). No extra space is used.

Report Article Issue

Comments: 38
s961206's avatar
Read More

Approach 4 can be more readable:

    int m = grid.length, n = grid[0].length;
    for(int i = 1; i < m; ++i) grid[i][0] += grid[i - 1][0];
    for(int j = 1; j < n; ++j) grid[0][j] += grid[0][j - 1];
    
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n; ++j){
            grid[i][j] += Math.min(grid[i-1][j], grid[i][j-1]);
        }
    }
    return grid[m-1][n-1];

120
Show 6 replies
Reply
Share
Report
SherMM's avatar
Read More

Dijkstra might be overkill here, but it also works.

50
Show 5 replies
Reply
Share
Report
survive's avatar
Read More

I don't think modify the original matrix is a good idea

39
Show 3 replies
Reply
Share
Report
ktmbdev's avatar
Read More

The reason why DP works here (but not in an actual shortest distance problem) is because we can only move right and down through the matrix. If we can move in all 4 directions, DP would give the wrong answer.

24
Show 8 replies
Reply
Share
Report
csgod's avatar
Read More

why're we starting at the bottom right corner?

9
Show 3 replies
Reply
Share
Report
madno's avatar
Read More

Interesting that we have the restriction on the input values of non-negative numbers.
The DP solution apparently works for negative numbers as well.

4
Reply
Share
Report
ping_pong's avatar
Read More

Shouldn't the complexity of first approach be O(2M*N). Why (M+N)?

6
Show 2 replies
Reply
Share
Report
sys526939916's avatar
Read More

are we allowed to move up or move to the left in this problem?

3
Show 5 replies
Reply
Share
Report
adarshdesai03's avatar
Read More

overwriting the inputs, how is that O(1) space? I was asked in some interviews specifically that inputs are read only! please correct me if my understanding is not right, thanks.

2
Show 2 replies
Reply
Share
Report
junlzhan's avatar
Read More

A Java solution that runs from the top-left to bottom-right:

    public int minPathSum(int[][] grid) {
        int m = grid.length + 1;
        int n = grid[0].length + 1;
        int[][] dp = new int[m][n];
        
        for(int i=1; i<m; i++){
            for(int j=1; j<n; j++){
                if(j==1)
                    dp[i][j] = dp[i-1][j] + grid[i-1][j-1];
                else  if (i==1)
                    dp[i][j] = dp[i][j-1] + grid[i-1][j-1];
                else
                    dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i-1][j-1];
            }
        }
        
        return dp[m-1][n-1];
    }

1
Reply
Share
Report
Time Submitted
Status
Runtime
Memory
Language
03/25/2021 12:58Accepted8 ms9.7 MBcpp
/23
Your previous code was restored from your local storage.Reset to default
Contribute
|||
Saved
Trie
This list is empty.